1. Field Of The Invention
The present invention relates to computer displays. More specifically, the present invention relates to a method for the approximation of caps of line segments on computer displays.
2. The Background
A computer display is made up of rows and columns of pixels. Each pixel may be very small. However, computer display technology has not yet advanced to the point where the pixels are small enough to avoid several limitations encountered when graphics are viewed by the human eye.
Sampling of images to be displayed on a computer, or of equations representing lines, results in a somewhat jagged appearance, also called the xe2x80x9cstaircasexe2x80x9d effect. This is due to the fact that the sampling process digitizes coordinate points on an object or line to discrete integer pixel positions, resulting in an image having staggered edges. This distortion is also called xe2x80x9caliasingxe2x80x9d. FIG. 1 is a diagram illustrating the staircase effect. Line 100 is sampled and then displayed using a group of shaded pixels 102. One can see by viewing the shaded pixels 120 that they appear jagged and suffer from the staircase effect.
Techniques used to decrease the aliasing suffered in computer graphics are known collectively as antialiasing techniques. The most obvious antialiasing technique is to simply increase the resolution of the display, so that each pixel is smaller. However, as discussed earlier, computer monitor technology as of yet does not provide for a display with such small pixels that aliasing is not viewable to the human eye.
A common antialiasing method is to increase the sampling rate by treating the display as if it were covered by a finer grid than it really is. This is known as supersampling. Supersampling works best on displays which are capable of displaying pixels at different intensities. In these displays, each pixel is actually made up of many subpixels, which can be turned on or off in certain patterns to give the pixel a specific intensity.
Typical supersampling techniques attempt to smooth the staircase effect by using the surrounding pixels. FIG. 2 is a diagram illustrating a supersampling technique applied to the aliased line of FIG. 1. The group of shaded pixels 200 is now much wider than in FIG. 1, and there is less of a staircase effect simply because they are wider. However, this technique also utilizes the ability to vary intensity of each pixel to smooth the edges of the line. For example, without the ability to vary intensities, pixel 202 would have to be completely shaded. However, by selectively turning on or off certain subpixels within pixel 202, it give the viewer the impression that only a region of pixel 202 is filled, and thus makes the line appear much smoother.
One drawback to supersampling is that identifying subpixels to be selectively turned on and off requires a larger number of calculations than simply determining which pixels are along a line path. These calculations are further complicated by the fact that the position of the line path within each pixel varies depending on the slope of the line. In a 45-degree line, the line path cuts each pixel in half diagonally, but a 30-degree line path does not.
Endpoints of a line, also known as caps, require very complex calculations, such as inverse squares. FIG. 3 is a diagram illustrating a single pixel containing an end-point of a line. The mathematical line 300 is known, and therefore the length of segment c can be determined fairly easily. However, the area of the entire shaded region 302 must be determined in order to determine the intensity of the pixel and the orientation of the subpixels. This involves numerous computations using the Pythagorean theorem, beginning with determining a from b and c (according to the Pythagorean theorem, a2+b2=c2, so in order to determine a, a square root, or in computer terms inverse root must be computed).
Similar computations must be made to determine the xe2x80x9cmiddlexe2x80x9d of the line, or the segment portion. Thus, repeated complex calculations must be made, which can create problems with limited processing power.
Line segments are represented as mathematical equations. Each segment will have a starting point, and ending point, and a slope. While some line segments may be relatively easy to draw on a computer display, such as precisely horizontal or vertical lines, most lines require some degree of approximation in choosing which pixels to illuminate in order to best represent the line segment to a viewer.
FIG. 4 is a diagram illustrating a line segment overlaid on a group of pixels. As can be seen, decisions must be made as to which pixels should be illuminated. For example, in column 2, a decision must be made between pixel 400 and pixel 402.
A common method for determining which pixels to illuminate to best represent a line segment is Bresenham""s line algorithm. In Bresenham""s approach, for lines with slopes between 0 and 1, pixel positions along a line segment are determined by sampling the line in one-pixel increments. Therefore, the process starts at the starting point 404 and steps to each successive column. At each column, the pixel is chosen whose y value is closest to the line segment.
Starting from the left end-point (x0,y0) of a given line, the process steps to each successive column (x position) and illuminates the pixel whose scan-line y value is closest to the line segment. FIG. 5 is a diagram illustrating the kth step in this process. Assuming that the pixel at (xk,yk) is to be displayed, the process needs to determine which pixel to plot in column xk+1. The choices are the pixels at positions (xk+1,yk) and (xk+1,yk).
At sampling position xk+1, the vertical pixel separations from the mathematical line path may be termed d1 and d2. The y coordinate on the mathematical line segment at pixel column position xk+1 is calculated as
y=m(xk+1)+b
where m=dy/dx
Then
d1=yxe2x88x92yk
d1=m(xk+1)+bxe2x88x92yk
d2=(yk+1)xe2x88x92y
d2=yk+131 m(xk+1)xe2x88x92b
The difference between these two separations is
d1xe2x88x92d2=2m(xk+1)xe2x88x922yk+2bxe2x88x921
The decision parameter pk for the kth step in the line process may be determined by rearranging the equations so that they only involve integer calculations. This may be accomplished by substituting m=xc2x7y/xc2x7x, where xc2x7y and xc2x7x are the vertical and horizontal separations of the endpoint positions, and defining:
pk=xc2x7x(d1xe2x88x92d2)
pk=2xc2x7yxc2x7xkxe2x88x922/xc2x7xxc2x7yk+c
The sign of pk is the same as the sign of d1xe2x88x92d2, since in the present case xc2x7x greater than 0. Parameter c is constant and has the value 2xc2x7y+xc2x7x(2bxe2x88x921), which is independent of pixel position and will be eliminated in the recursive calculations for pk. If the pixel at yk is closer to the line path than the pixel at yk+1 (that is, d1 less than d2), then decision parameter pk is negative. In that case, the lower pixel is illuminated, otherwise the upper pixel is illuminated.
Coordinate changes along the line occur in unit steps in either the x or y directions. Therefore, the values of successive decision parameters can be obtained using incremental integer calculations. At step k+1, the decision parameter is evaluated as
Pk+1=pk+2xc2x7yxc2x7xk+1xe2x88x922xc2x7xxc2x7yk+1+c
Subtracting pk=2xc2x7yxc2x7xkxe2x88x922/xc2x7xxc2x7yk+c from the preceding equation, we have
Pk+1pk=2xc2x7y(xk+1xe2x88x92xk)xe2x88x922xc2x7x(yk+1+yk)
But xk+1=xk+1, so that
Pk+1=pk+2xc2x7yxe2x88x922xc2x7x(yk+1+yk)
where the term yk+1+yk is either 0 or 1, depending on the sign of parameter pk.
This iterative calculation of decision parameters is performed at each integer x position, starting at the left coordinate endpoint of the line. The first parameter, p0, is evaluated at the starting pixel position (x0, y0) and with m evaluated as xc2x7y/xc2x7x:
p0+2xc2x7yxe2x88x92xc2x7x
Bresenham""s method may be summarized as follows (for slope value between xe2x88x921 and 1):
1. Begin with starting point (x0, y0)
2. calculate the following constants:
xcex94xxe2x80x94the change in x over the entire line segment
xcex94yxe2x80x94the change in y over the entire line segment
2xcex94y
2xcex94yxe2x88x922xcex94x
3. Calculate the starting value for the decision parameter (p) as
p0=2xcex94yxe2x88x92xcex94x
4. At each xk, along the line segment, starting at k=0, perform the following test: if pk less than 0, the next point to plot is (xk+1, yk) and
xe2x80x83pk+1=pk+2xcex94y
Otherwise, the next point to plot is (xk+1, yk+1) and
pk+1=pk+2xcex94yxe2x88x922xcex94x
5. Repeat step 4 for each column until the ending point is reached.
An inverse root is one of the most complicated computations a processor can make. In recent years, there has been movement away from powerful mainframe computers to smaller, cheaper, less powerful processors, such as those that may be contained in hand-held computers or laptop computers. These types of processors, due to market pressures, are therefore very cost and size sensitive.
While in a large computer, antialiasing techniques may be applied using hardware, such as graphics cards, the space may not be available for such hardware in these smaller, less powerful processors. Additionally, the cost of implementing the techniques in hardware may be prohibitive. Therefore, it would be preferable to perform such techniques using software.
However, performing the traditional antialiasing in software would take too much processing power due to all the inverse squares that would have to be calculated, which would slow down the processor to intolerable levels. What is needed is a solution which allows for an antialiasing technique to be applied and approximation of line segments to be performed which could be performed by software but which do not use as much processing power as traditional techniques.
The middle of line segments may be drawn on a computer display using an iterative method that reduces the number of calculations required. The process is repeated for each column. The first pixel is plotted according to a formula that allows the first pixel to best represent the location of the line in the column. A second pixel is then plotted either above, below, to the left of, or the right of the first pixel depending on the direction of the line. A normalized intensity value between 0 and 1.0 is then assigned to the first pixel according to the amount of area above, below, to the left of, or the right of the line in the first pixel depending on the direction of the line. This value may be assigned using a variable computed in plotting the first pixel. A normalized intensity value for the second pixel equal to 1.0 minus the normalized intensity value of the first pixel may then be assigned. Finally, the first and second pixels are shaded according to the normalized intensity values.